package com.lili.greedy;

import java.util.*;

/**
 * @Auther: 李 力
 * @Date: 2024/8/6
 * @Description: 分数背包问题
 * @version: 1.0
 */
public class ScoreAndBeiBao {
    /*
    1. n个物品都是液体，有重量和价值
    2. 现在你要取走 10升 的液体
    3. 每次可以不拿，全拿，或拿一部分，问最高价值是多少

       编号 重量(升) 价值  名称
        0   4       24      水
        1   8       160     牛奶
        2   2       4000    五粮液
        3   6       108     可乐
        4   1       4000    茅台

        简化起见，给出的数据都是【价值/重量】能够整除，避免计算结果中出现小数，增加心算难度
     */
    //total：总的升数
    public static Map<String, Integer> select(Item[] items, int total) {
        //排序原来的数组，按照单位价值排,降序排序，从大到小
        Arrays.sort(items, Comparator.comparingInt(Item::getUnitValue).reversed());
        //最大价值
        int maxNum = 0;
        HashMap<String, Integer> map = new HashMap<>();
        for (Item item : items) {
            if (total >= item.getWeight()) {
                //可以拿完  7
                total = total - item.getWeight();
                maxNum = maxNum + item.getValue();
                map.put(item.getName(), item.getWeight());
            } else {
                //拿不完
                int sum = total * item.getUnitValue();
                maxNum = maxNum + sum;
                map.put(item.getName(), total);
                break;
            }
        }
        map.put("最大价值", maxNum);
        return map;
    }

    public static void main(String[] args) {
        Item[] items = new Item[]{
                new Item(0, 4, 24, "水"),
                new Item(1, 8, 160, "牛奶"),
                new Item(2, 2, 4000, "五粮液"),
                new Item(3, 6, 108, "可乐"),
                new Item(4, 1, 4000, "茅台"),
        };
        Map<String, Integer> map = ScoreAndBeiBao.select(items, 10);
        map.forEach((key, value) -> {
            System.out.println(key + ":" + value);
        });
    }
}
